面试题 17.05. 字母与数字

Similar Question

Solution Tips

方案一: 前缀和 + 哈希表

var findLongestSubarray = function (array) {
    // 与 1248 一模一样
    // 规定数字为 1, 字母为 -1 即可
    const map = {};
    let maxLen = 0;
    let res = [0, -1];
    let prefixSum = 0;
    for (let i = 0; i < array.length; i++) {
        const item = /\d/g.test(array[i][0]) ? 1 : -1;
        prefixSum += item;
        if (map[prefixSum] === undefined) {
            // 不需要数组, 最早出现的索引最小, 距离最远, 贪心, 更符合题意
            map[prefixSum] = i;
        }

        if (prefixSum === 0) {
            // 当前的就是符合题意的
            const len = i + 1;
            if (len > maxLen) {
                maxLen = len;
                res = [0, i]
            }
        }

        // 寻找自己
        if (map[prefixSum] !== undefined) {
            const len = i - map[prefixSum];
            if (len > maxLen) {
                maxLen = len;
                res = [map[prefixSum] + 1, i]
            }
        }
    }

    return array.slice(res[0], res[1] + 1);
};